import time
from random import randint
def backpack_recu(W , w , v , n):
    """用分治算法思想来写递归函数求解背包最大价值"""
    if n == 0 or W == 0 : # 递归退出条件：没有物品，或者承重最大值W为0
        return 0 # 都是返回0
    # 分解问题
    if (w[n-1] > W):
         # 若第n件物品的重量大于W，只能选择第一种情况，不放入第n个物品
        return backpack_recu(W , w , v , n-1)
    else:
        # 比较放入第n个物品和不放入第n个物品两个价值比较
        v1 = v[n-1] + backpack_recu(W-w[n-1], w , v , n-1) # 放入第n个物品
        v2 = backpack_recu(W , w , v , n-1) # 不放入第n个物品
        return max(v1,v2) # 合并结果取最大价值

def backpack_dp(W, w, v, n):
    """动态规划算法思想来解决问题"""
    # 初始化数组dp保存子问题的解
    dp = [[0 for wi in range(W + 1)]
          for i in range(n + 1)]
    for i in range(n + 1):
        for wi in range(W + 1):
            # 没有物品，或者承重最大值W为0
            if i == 0 or wi == 0:
                dp[i][wi] = 0  # 最大价值为0
            elif w[i - 1] <= wi:
                # 比较放入第n个物品和不放入第n个物品两个价值比较
                v1 = v[i - 1] + dp[i - 1][wi - w[i - 1]]  # 放入第n个物品
                v2 = dp[i - 1][wi]  # 不放入第n个物品
                dp[i][wi] = max(v1, v2)  # 取最大价值
            else:
                # 若第n件物品的重量大于W，只能选择第一种情况，不放入第n个物品
                dp[i][wi] = dp[i - 1][wi]
    return dp[n][W]  # 最大值必然在这里

if __name__ == '__main__':
    for n in range(5, 24): # 测试n从5到19
        val = []
        wt = []
        W = n * 40 # 背包重量与物品数量成正比提升
        for i in range(n):
            val.append(randint(5, 300)) # 随机产生物品的价值
            wt.append(randint(1,80)) # 随机产生物品的重量
        start = time.clock()  # 记录程序开始时间
        r1 = backpack_dp(W, wt, val, n)
        t1 = time.clock() - start # 程序运行时间
        start = time.clock()
        r2 = backpack_recu(W, wt, val, n)
        t2 = time.clock() - start
        print("n={},W={}".format(n, W))
        print("动态规划结果：{}，用时：{}".format(r1,t1))
        print("分治结果：{}，用时：{}".format(r2,t2))
